package 蓝桥._2024.砍柴;

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main2 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int T = scan.nextInt();
        int[] lens = new int[T];
        for (int i = 0; i < T; i++) {
            lens[i] = scan.nextInt();
        }
        // 素数筛
        int max = 100010;
        boolean[] isPrime = new boolean[max];
        for (int i = 2; i < max; i++) {
            isPrime[i] = true;
        }
        for (int i = 2; i < max; i++) {
            if (isPrime[i]) {
                for (int j = i + i; j < max; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        List<Integer> primeSet = new ArrayList<>();
        List<Integer> failSet = new ArrayList<>(); // 先手必败
        failSet.add(0);
        failSet.add(1);

        for (int i = 2; i < max; i++) {
            if (isPrime[i]) {
                if(!isPrime[i+1]&&!failSet.contains(i+1)) failSet.add(i+1);
                if(!isPrime[i+2]&&!failSet.contains(i+2)) failSet.add(i+2);
            }
        }
        System.out.println(failSet);
        for (int i = 0; i < T; i++) {
            if(failSet.contains(lens[i]))
                System.out.println("0");
            else
                System.out.println("1");
        }





        scan.close();
    }
}